import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class code1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        ListNode node = new ListNode(-1);
        for(int i=0;i<lists.size();i++) {
            node.next = mergeKTwoLists(node.next,lists.get(i));
        }
        return node.next;
    }

    private ListNode mergeKTwoLists(ListNode head1,ListNode head2) {
        //特殊情况
        if(head1 == null) return head2;
        if(head2 == null) return head1;

        ListNode node = new ListNode(-1);
        ListNode cur = node;

        while(head1!=null && head2!=null) {
            if(head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }

        if(head1 != null) {
            cur.next = head1;
        }

        if(head2 != null) {
            cur.next = head2;
        }

        return node.next;
    }
}